/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/partition-equal-subset-sum
   @Language: C++
   @Datetime: 19-05-09 16:54
   */

class Solution {
public:
	/**
	 * @param nums: a non-empty array only positive integers
	 * @return: true if can partition or false
	 * Tip: 0-1 backpack
	 */
	bool canPartition(vector<int> &nums) {
		// write your code here
		int sum=0;
		for(int i=nums.size(); i--; sum+=nums[i]);
		if(sum&1) return false;
		sum=sum>>1;
		vector<int> dp(sum+1,0);
		for(int i=0; i<nums.size(); ++i){
			for(int j=sum; j; --j)
				if(j>=nums[i]) dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
		}
		return dp[sum]==sum;
	}
};
